package com.practice.dsa.interviewclassic6;

import java.util.*;

/**
 * 描述 字符唯一
 * 面试题 01.01. 判定字符是否唯一
 * 简单
 * 实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
 *
 * 示例 1：
 *
 * 输入: s = "leetcode"
 * 输出: false
 * 示例 2：
 *
 * 输入: s = "abc"
 * 输出: true
 * 限制：
 *
 * 0 <= len(s) <= 100
 * s[i]仅包含小写字母
 * 如果你不使用额外的数据结构，会很加分。
 * @author yaokun.zhang
 * @version 1.0
 * @date 2022-11-08 10:46:30
 */
public class CharUnique {

    /**
     * 第一种：双重循环
     *
     * 时间复杂度O(n^2)
     * @param astr
     * @return
     */
    public boolean isUnique1(String astr) {
        int length = astr.length();
        for(int i = 0 ; i < length - 1; i ++){
            for(int j = i + 1 ; j < length; j ++){
                if(astr.charAt(i) == astr.charAt(j)){
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 空间换算时间
     * 时间复杂度O(n)
     * 使用HashSet 主要特性：hash插入代价低，查找快
     * 其他特性：乱序不重复
     * @param astr str
     * @return
     */
    public boolean isUnique2(String astr) {
        int length = astr.length();
        Set<Character> set  = new HashSet<>();
        for(int i = 0 ; i < length; i ++){
            if(set.contains(astr.charAt(i))){
                return false;
            }
            set.add(astr.charAt(i));
        }
        return true;
    }

    /**
     * - 计算步长
     * - 位移获取当前字节数
     * - 位与运算判断是否有重复数据
     * - 位或运算记录遍历数据
     * 时间复杂度O(1)
     * @param astr
     * @return
     */
    public boolean isUnique3(String astr) {
        //历史记录
        int a = 0;
        //初始化
        int b = 1;

        for(int i = 0 ; i < astr.length(); i ++){
            //计算步长
            char t = astr.charAt(i);
            int offset = t - 'a';
            //位移获取当前数
            int cur = b << offset;
            if((a & cur) != 0){
                return false;
            }
            a |= cur;
        }
        return true;
    }

    public static void main(String[] args) {
        Map<Character, Integer> map = new HashMap<>();

    }
}
